//以课件上摸红白球为例
public class Viterbi {
    static private int[] status = { 0, 1, 2 };          //0,1,2三种隐状态,用Q表示，代表三个盒子
    static private int[] observations = {1,2,1};       //观测序列,可能的取值范围为1~2,用O表示，代表红白球
    //transititon_probability[i][j]为从隐状态i转移到隐状态j的概率，即P{Q(t+1)=j|Q(t)=i}
    static double[][] transititon_probability = new double[][] { { 0.5, 0.2, 0.3 },
            { 0.3, 0.5, 0.2 }, { 0.2, 0.3, 0.5 } };     //上一次从盒子i摸的条件下，这次从盒子j摸的概率
    //初始pai[i]为初始为隐状态i的概率，即P{Q(0)=i}
    static private double[] pai = new double[] { 0.2, 0.4, 0.4 };       //第一次从盒子i摸的概率
    //B[i][j]为在隐状态i,观测值为j+1的概率，即P{O(t)=j+1|Q(t)=i}，即从盒子i摸到颜色为j+1球的概率
    public static double[][] B = {{0.5,0.5},{0.4,0.6},{0.7,0.3} };

    /**
     * 求解HMM模型
     *
     * @param obs
     *            观测序列
     * @param states
     *            隐状态
     * @param start_p
     *            初始概率（隐状态）
     * @param trans_p
     *            转移概率（隐状态）
     * @param emit_p
     *            发射概率 （隐状态表现为显状态的概率）
     * @return 最可能的序列
     */
    public static int[] compute(int[] obs, int[] states, double[] start_p, double[][] trans_p, double[][] emit_p) {
        int N = B.length;                  //状态个数

        //T=t时，delta[i]=P{Q(t-1)=i,O(t-1)=obs[t-1]}，
        // delta[i]即上一时刻观测值obs[t-1]已被观测的情况下，其由隐状态i发射的概率
        double[] delta = new double[states.length];
        //path[i][j]=argmax/u (P{Q(j-1)=u,Q(j)=i})=argmax/u (P{Q(j)=i|Q(j-1)=u}*P{Q(j-1)=u}),
        // path[i][j],即状态i在t=j时刻最有可能从哪个状态转移而来
        int[][] path = new int[states.length][obs.length];

        //第一次观测无状态转移，只做初始化
        for (int i = 0; i < N; i++) {
            delta[i] = start_p[i] * emit_p[i][obs[0]-1];
            path[i][0] = 0;
        }


        //t为时间
        for (int t = 1; t < obs.length; ++t) {
            double temp[] = { delta[0], delta[1], delta[2] };

            //j为当前层取j
            for (int j = 0; j < N; j++) {
                double maxProb = -1;
                //i为上一层取i
                for (int i = 0; i < N; i++) {
                    double nprob = temp[i] * trans_p[i][j];
                    if (nprob > maxProb) {
                        maxProb = nprob;
                        // 记录路径，当前的j是从上次的i转移而来
                        path[j][t]=i;
                    }
                    // 记录较大概率
                    delta[j] = maxProb * emit_p[j][obs[t] - 1];
                }
            }
        }

        //确定最后一次观测的隐状态
        double prob = -1;
        int state = 0;
        for (int i = 0; i < N; i++) {
            if (delta[i] > prob) {
                prob = delta[i];
                state = i;                  //最后一次的观测值已经被观测，其由隐状态state发射的概率最大
            }
        }

        //借助path数组不断回溯，找到由上一时刻哪个隐状态转移而来的概率最大，即认为上一时刻的隐状态取该值
        int []ret=new int[obs.length];
        ret[obs.length-1]=state;
        int followedState=state;
        for(int i=obs.length-2;i>=0;i--){
            followedState=path[followedState][i+1];
            ret[i]=followedState;
        }

        return ret;
    }

    public static void main(String[] args) {
        int[] result = Viterbi.compute(observations, status, pai, transititon_probability, B);
        for (int r : result) {
            System.out.print((r + 1) + " ");
        }
    }



}